package leetcode.day_2021_03_8_2021_03_14;

/**
 * 55. 跳跃游戏
 * https://leetcode-cn.com/problems/jump-game/
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 */
public class LeetCode0055 {
    public static int canJump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i=1; i<n; i++) {
            dp[i] = cal(nums, dp, i);
        }
        return dp[n-1];
    }

    public static int cal(int[] nums, int[] dp, int index) {
        int min = Integer.MAX_VALUE;

        for(int i=0; i<=index-1; i++) {
            if (index-i <= nums[i]) {
                min =  Math.min(min, dp[i]+1);
            }
        }
        return min;
    }
    // ============================================ [2,3,1,1,4]
    // 失败
    public static boolean canJump2(int[] nums) {
        int n = nums.length;
        // 一个一个的试，且值不能为0
        for (int beginIndex=0; beginIndex<n&&nums[beginIndex]!=0; beginIndex++) {
            // 定义终点
            int end = 0;
            // 起点
            int start = beginIndex;
            while (end < n) {
                end = end + nums[start];
                start = end;
                // 跳到0位置
                if (start<n && nums[start] == 0) break;
            }
            if (end>=n) return true;
        }
        return false;
    }

    public static boolean canJump3(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++)
        {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }


    public static void main(String[] args) {
        System.out.println(canJump3(new int[]{2,3,1,1,4}));
//        System.out.println(canJump3(new int[]{3,2,1,0,4}));
    }
}
